package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no22;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> resultList = solution.generateParenthesis2(4);
        resultList.stream().map(o -> o + " ").forEach(System.out::print);
        System.out.println();
        Set<String> set = new HashSet<>();
        for (String s : resultList) {
            if (!set.add(s)) {
                System.out.println(s);
            }
        }
        System.out.println(set.size());
        System.out.println(resultList.size());
        System.out.println(set.contains("((()))((()))"));
        System.out.println(set.contains("(())(())(())"));

    }


    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        if (n > 0) {
            Set[] dp = new HashSet[n + 1];
            dp[0] = new HashSet();
            dp[0].add("");
            dp[1] = new HashSet();
            dp[1].add("()");
            for (int i = 2; i <= n; i++) {
                dp[i] = new HashSet();
                for (int j = 1; j <= i - 1; j++) {
                    Set<String> left = dp[j];
                    Set<String> right = dp[i - j - 1];
                    for (String l : left) {
                        for (String r : right) {
                            dp[i].add("()" + l + r);
                            dp[i].add("(" + l + ")" + r);
                            dp[i].add(l + "()" + r);
                            dp[i].add("(" + l + r + ")");
                            dp[i].add(l + "(" + r + ")");
                        }
                    }
                }
            }
            resultList.addAll(dp[n]);
        }
        return resultList;
    }

    public List<String> generateParenthesis2(int n) {
        List<String> resultList = new ArrayList<>();
        char[] chars = new char[n * 2];
        Set<String> resultSet = new HashSet<>();
        find(chars, n, 0, 0, 0, resultSet);
        resultList.addAll(resultSet);
        return resultList;
    }

    public void find(char[] chars, int n, int curIndex, int l, int r, Set<String> resultSet) {
        if (curIndex == n * 2) {
            resultSet.add(new String(chars));
            return;
        }
        if (r < l) {
            chars[curIndex] = ')';
            find(chars, n, curIndex + 1, l, r + 1, resultSet);
        }
        if (l < n) {
            chars[curIndex] = '(';
            find(chars, n, curIndex + 1, l + 1, r, resultSet);
        }
    }
}
